package com.south.base.test.arithmetic.dynamic.programming;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author Administrator
 * @date 2019/12/4 9:45
 */
public class IntegerBreak {
    /**
     * 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
     */
    @Test
    public void integerBreak() {
        Assert.assertEquals(1, integerBreak(2));
        Assert.assertEquals(36, integerBreak(10));
        Assert.assertEquals(36, integerBreak2(10));
    }

    public int integerBreak(int n) {
        int p = n % 3, q = n / 3, r = p + (2 * p + 1) % 5;
        return n <= 3 ? n - 1 : (int) (Math.pow(3, q - (p & 1)) * r);
    }


    public int integerBreak2(int n) {
        //memo用于存储memo[i]已经计算过当前数字i的最大乘积，memo[0]无用，因而length为n+1
        int[] memo = new int[n + 1];
//        Arrays.fill(memo, -1);
        return breakInteger(n, memo);
    }

    private int breakInteger(int n, int[] memo) {
        if (n == 1) {
            return 1;
        }
        if (memo[n] != 0) {
            return memo[n];
        }
        int res = -1;
        for (int i = 1; i <= n - 1; i++) {
            res = max(res, i * (n - i), i * breakInteger(n - i, memo));
        }
        memo[n] = res;
        return res;
    }

    private int max(int a, int b, int c) {
        return Math.max(a, Math.max(b, c));
    }

}
